/***
 * 双指针 滑窗
 * 58.II. 左旋转字符串
 * 57.II. 和为s的连续正数序列
 * 21. 调整数组顺序使奇数位于偶数前面
 * 58.I. 翻转单词顺序
 * 48. 最长不含重复字符的子字符串
 * **/

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    typename T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    // 58.II
    void reverseInplace(string &s, int left, int right)
    {
        while (left < right) {
            swap(s[left++], s[right--]);
        }
    }
    string reverseLeftWords(string s, int n)
    {
        n %= s.size();
        // 空间O(N)
#if 0
        return s.substr(n, s.size() - n) + s.substr(0, n);
#endif
        // 原地旋转
        reverseInplace(s, 0, n - 1);
        reverseInplace(s, n, s.length() - 1);
        reverseInplace(s, 0, s.length() - 1);
        return s;
    }

    // 57.II.
    vector<vector<int>> findContinuousSequence(int target)
    {
        // 枚举 双循环
#if 0
        vector<vector<int>> res;
        vector<int> ans;
        int sum = 0;
        for (int i = 1; i <= target / 2; ++i) {
            ans.clear(); // 此后调用size()返回零 capacity不变
            for (int j = i;; ++j) {
                sum += j;
                ans.push_back(j);
                if (sum > target) {
                    sum = 0;
                    break;
                } else if (sum == target) {
                    res.emplace_back(ans); // 原地构造
                    sum = 0;
                    break;
                }
            }
        }
        return res;
#endif
        // 滑窗 单循环
        vector<vector<int>> res;
        int sum = 0;
        int i = 1, j = 1;
        while (i <= j && j <= target / 2 + 1) {
            sum += j;
            while (sum > target) {
                sum -= i;
                ++i;
            }
            if (sum == target) {
                vector<int> ans;
                for (int idx = i; idx <= j; ++idx) {
                    ans.emplace_back(idx);
                }
                res.emplace_back(ans);
                sum -= i;
                ++i;
            }
            ++j;
        }
        return res;
    }
    // 21.
    vector<int> exchange(vector<int> &nums)
    {
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            while (i < j && nums[i] % 2 != 0) {
                ++i;
            }
            while (i < j && nums[j] % 2 == 0) {
                --j;
            }
            // i 偶数 j 奇数
            swap(nums[i++], nums[j--]);
        }
        return nums;
    }
    // 58.I.
    string reverseWords(string s)
    {
        // 忽略多余空格，标点当做单词一部分
        // 倒序遍历
        string res;
        for (int j = s.length() - 1; j >= 0; --j) {
            while (j >= 0 && s[j] == ' ') { // 寻找右边界
                --j;
            }
            int i = j;
            while (i >= 0 && s[i] != ' ') { // 寻找左边界
                --i;
            }
            res += s.substr(i + 1, j - i); // 加入答案
            res += ' ';
            j = i;
        }
        while (res.back() == ' ') {
            res.pop_back();
        }
        return res;
    }
    // 48.
    int lengthOfLongestSubstring(string s)
    {
        // 滑窗
        int n = s.length();
        int i = 0, j = 0;
        int res = 0;
        vector<int> count(128, 0); // 128 ASCII
        while (i <= j && j < n) {
            while (j < n && count[s[j]] == 0) { // 右边界
                ++count[s[j++]];
            }
            res = max(res, j - i);
            while (j < n && s[i] != s[j]) { // 左边界
                --count[s[i++]];
            }
            --count[s[i++]];
        }
        return res;
    }
};

Solution solve = Solution();

void test58II()
{
    string s = "abcdefg";
    int n = 9;
    cout << solve.reverseLeftWords(s, n) << endl;
}

void test57II()
{
    vector<vector<int>> nums = solve.findContinuousSequence(9);
    for (auto &num : nums) {
        print(num);
    }
}

void test58I()
{
    string s = "  hello   world!  ";
    cout << solve.reverseWords(s) << endl;
}

void test48()
{
    string s = "bbbbbb";
    cout << solve.lengthOfLongestSubstring(s) << endl;
}

int main()
{
    // test58II();
    // test57II();
    // test58I();
    // test48();
    return 0;
}